/* 
 * File:   dfa.h
 * Author: abhi
 *
 * Created on February 17, 2012, 9:20 PM
 */

#ifndef DFA_H
#define	DFA_H

#include "nfa.h"

#ifdef	__cplusplus
extern "C" {
#endif
    
    typedef struct DFA_State_t {
        int* nfaStateIndices; /* Index of nfa states */
        int nfaStatesNum; /* Number of nfa states */
        int id; /* unique identifier of state */
    } DFAState;
    
    typedef struct DFA_t {
        NFA* nfa; /* source NFA */
        NextClosureStates* nfaNextClosures; /* closures */
        DFAState* states; /* Q */
        int statesNum;
        int initStateIndex; /* q0 */
        Transition* transTbl; /* δ */
        int transTblSize;        
        int* finalStatesIndices; /* F */
        int finalStatesNum;
    } DFA;
    
    typedef struct DFA_State_Queue_Element_t {
        DFAState* state;
        struct DFA_State_Queue_Element_t* next;
    } DFAStateQueueElement;
    
    typedef struct DFA_State_Queue_t {
        DFAStateQueueElement* front;
        DFAStateQueueElement* rear;
        int size;
    } DFAStateQueue;
    
    /* DFA methods */
    void addState(DFA* dfa, DFAState newState);
    void addTransition(DFA* dfa, int srcStateIndex, int symbolIndex, int dstStateIndex);
    int pow2(int exponent);
    void setID(DFAState* dfaState);
    int searchDFAState(DFA* dfa, DFAState dfaState);
    void labelDFAFinalStates(DFA* dfa);
    DFA* getDFAForNFA(NFA* inputNFA, NextClosureStates* inputNFANextClosures);
    void printDFA(DFA* dfa);
    
    /* DFA Queue methods */
    DFAStateQueue* createDFAStateQueue(void);
    void enQueue(DFAStateQueue* dfaStateQueue, DFAState* dfaState);
    DFAState* deQueue(DFAStateQueue* dfaStateQueue);
    int isEmpty(DFAStateQueue* dfaStateQueue);
    

#ifdef	__cplusplus
}
#endif

#endif	/* DFA_H */

